import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description: Leetcode: 77. 组合
 *<a href="https://leetcode.cn/problems/combinations/submissions/">...</a>
 * User: DELL
 * Date: 2023-07-14
 * Time: 23:04
 */
public class Solution {
    /**
     * 解法一: (dfs)
     * 总体思想就是利用dfs的递归+回溯遍历每一种可能的组合情况,
     * 但是总体的程序效率较慢.即,有很多无用的递归.因此需要优化
     * @param n
     * @param k
     * @return
     */
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        // 题目规定输入合法,因此不需要进行合法性检验
        Deque<Integer> temp = new LinkedList<>();
        dfs(res,n,k,1,temp);
        return res;
    }

    /**
     * dfs遍历所有可能情况
     * @param res    存储结果
     * @param n      数字的最大值
     * @param k      选取的数字数量
     * @param curNum 当前遍历的数字
     * @param temp   临时存放选取的数字
     */
    private void dfs(List<List<Integer>> res, int n, int k, int curNum, Deque<Integer> temp) {
        if (curNum > n) {
            if (temp.size() == k) {
                res.add(new ArrayList<>(temp));
            }
            return;
        }
        // 选择当前数字
        if (temp.size() != k) {
            temp.add(curNum);
            dfs(res, n, k, curNum+1, temp);
            temp.removeLast();
        }
        // 不选择当前数字
        dfs(res,n,k,curNum+1,temp);
    }


    /**
     * 解法二: (dfs+剪枝)
     * 在方法一中我们很容易的发现我们做了很多的无用的遍历,比如剩下数字 + 已选择的数字的数量
     * 正好等于 k 时,我们就必须选择以后的每一个数字,不然不选择的就是无用遍历,因为最后数字的
     * 数量一定小于k
     * 剪枝方案如下:
     * 1. 判断如果当前已经选择了 k 个数字,则以后的遍历直接跳过,即默认不选,因为选择之后,选
     * 择的数量一定大于 k,即一定不满足,我们直接舍去
     * 2. 不许选择当前数字的前提是 (temp.size()+n-curNum+1) > k ,即当前数字不选取之后,
     * 剩余的数字加上已选取的数字的数量要大于等于 k ,否则不能不选取当前数字.
     * 经过以上两条方案的剪枝后,改程序已经超过了 99% 的用户代码了
     * 解法一的超过了不足 20%
     * @param n
     * @param k
     * @return
     */
    public List<List<Integer>> combine2(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        // 题目规定输入合法,因此不需要进行合法性检验
        Deque<Integer> temp = new LinkedList<>();
        dfs2(res,n,k,1,temp);
        return res;
    }

    /**
     * dfs遍历所有可能情况
     * @param res    存储结果
     * @param n      数字的最大值
     * @param k      选取的数字数量
     * @param curNum 当前遍历的数字
     * @param temp   临时存放选取的数字
     */
    private void dfs2(List<List<Integer>> res, int n, int k, int curNum, Deque<Integer> temp) {
        if (curNum > n) {
            if (temp.size() == k) {
                res.add(new ArrayList<>(temp));
            }
            return;
        }
        if (temp.size() == k) {
            dfs2(res,n,k,n+1,temp);
            return;
        }
        // 不选择当前数字
        if ((temp.size()+n-curNum+1) > k) {
            dfs2(res,n,k,curNum+1,temp);
        }
        // 选择当前数字
        temp.add(curNum);
        dfs2(res, n, k, curNum+1, temp);
        temp.removeLast();
    }
}